/**
 * @author xchen
 */
public class code_876 {
	public ListNode middleNode(ListNode head) {
		ListNode tailNode = head;
		ListNode middleNode = head;
		int i = 1;
		while (tailNode.next != null) {
			i++;
			tailNode = tailNode.next;
			if (i % 2 == 0) {
				middleNode = middleNode.next;
			}
		}
		return middleNode;
	}

	public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}
}
